{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find in Mountain Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #interactive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #交互"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findInMountainArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #山脉数组中查找目标值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>（这是一个 <strong>交互式问题&nbsp;</strong>）</p>\n",
    "\n",
    "<p>给你一个 <strong>山脉数组</strong>&nbsp;<code>mountainArr</code>，请你返回能够使得&nbsp;<code>mountainArr.get(index)</code>&nbsp;<strong>等于</strong>&nbsp;<code>target</code>&nbsp;<strong>最小</strong>&nbsp;的下标 <code>index</code>&nbsp;值。</p>\n",
    "\n",
    "<p>如果不存在这样的下标 <code>index</code>，就请返回&nbsp;<code>-1</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>何为山脉数组？如果数组&nbsp;<code>A</code> 是一个山脉数组的话，那它满足如下条件：</p>\n",
    "\n",
    "<p><strong>首先</strong>，<code>A.length &gt;= 3</code></p>\n",
    "\n",
    "<p><strong>其次</strong>，在&nbsp;<code>0 &lt; i&nbsp;&lt; A.length - 1</code>&nbsp;条件下，存在 <code>i</code> 使得：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>A[0] &lt; A[1] &lt; ... A[i-1] &lt; A[i]</code></li>\n",
    "\t<li><code>A[i] &gt; A[i+1] &gt; ... &gt; A[A.length - 1]</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>你将&nbsp;<strong>不能直接访问该山脉数组</strong>，必须通过&nbsp;<code>MountainArray</code>&nbsp;接口来获取数据：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>MountainArray.get(k)</code>&nbsp;- 会返回数组中索引为<code>k</code>&nbsp;的元素（下标从 0 开始）</li>\n",
    "\t<li><code>MountainArray.length()</code>&nbsp;- 会返回该数组的长度</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<p>对&nbsp;<code>MountainArray.get</code>&nbsp;发起超过 <code>100</code> 次调用的提交将被视为错误答案。此外，任何试图规避判题系统的解决方案都将会导致比赛资格被取消。</p>\n",
    "\n",
    "<p>为了帮助大家更好地理解交互式问题，我们准备了一个样例 &ldquo;<strong>答案</strong>&rdquo;：<a href=\"https://leetcode-cn.com/playground/RKhe3ave\" target=\"_blank\">https://leetcode-cn.com/playground/RKhe3ave</a>，请注意这 <strong>不是一个正确答案</strong>。</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>array = [1,2,3,4,5,3,1], target = 3\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>3 在数组中出现了两次，下标分别为 2 和 5，我们返回最小的下标 2。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>array = [0,1,2,4,2,1], target = 3\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>3 在数组中没有出现，返回 -1。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= mountain_arr.length() &lt;= 10000</code></li>\n",
    "\t<li><code>0 &lt;= target &lt;= 10^9</code></li>\n",
    "\t<li><code>0 &lt;= mountain_arr.get(index) &lt;=&nbsp;10^9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-in-mountain-array](https://leetcode.cn/problems/find-in-mountain-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-in-mountain-array](https://leetcode.cn/problems/find-in-mountain-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,3,1]\\n3', '[0,1,2,4,2,1]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "def binary_search(mountain, target, l, r, key=lambda x: x):\n",
    "    target = key(target)\n",
    "    while l <= r:\n",
    "        mid = (l + r) // 2\n",
    "        cur = key(mountain.get(mid))\n",
    "        if cur == target:\n",
    "            return mid\n",
    "        elif cur < target:\n",
    "            l = mid + 1\n",
    "        else:\n",
    "            r = mid - 1\n",
    "    return -1\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        l, r = 0, mountain_arr.length() - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        peak = l\n",
    "        index = binary_search(mountain_arr, target, 0, peak)\n",
    "        if index != -1:\n",
    "            return index\n",
    "        index = binary_search(mountain_arr, target, peak + 1, mountain_arr.length() - 1, lambda x: -x)\n",
    "        return index\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "\n",
    "\n",
    "        # 峰值是从左到右第一个满足条件的点\n",
    "        def checkpeek(x):\n",
    "            return mountain_arr.get(x+1) - mountain_arr.get(x) < 0\n",
    "        # left结果是左到右第一个满足条件的点\n",
    "        def checkleft(x):\n",
    "            return mountain_arr.get(x) >= target\n",
    "        # right结果是左到右第一个满足条件的点\n",
    "        def checkright(x):\n",
    "            return mountain_arr.get(x) <= target\n",
    "\n",
    "        def get_min_satisfied(l, r, f):\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if f(mid):\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return l\n",
    "        \n",
    "        n = mountain_arr.length()\n",
    "        peek = get_min_satisfied(0, n-2, checkpeek)\n",
    "        if mountain_arr.get(peek) < target:\n",
    "            return -1\n",
    "        \n",
    "        left = get_min_satisfied(0, peek, checkleft)\n",
    "        # 当相等的时候直接返回\n",
    "        if mountain_arr.get(left) == target:\n",
    "            return left\n",
    "        # 否则去找右边的\n",
    "        right = get_min_satisfied(peek+1, n-1, checkright)\n",
    "        if mountain_arr.get(right) == target:\n",
    "            return right\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, marr: 'MountainArray') -> int:\n",
    "        \n",
    "        def checkpeek(x):\n",
    "            return marr.get(x+1) - marr.get(x) < 0\n",
    "        \n",
    "        def checkleft(x):\n",
    "            return marr.get(x) >= target\n",
    "        \n",
    "        def checkright(x):\n",
    "            return marr.get(x) <= target\n",
    "        \n",
    "        n = marr.length()\n",
    "        \n",
    "        def get_min_satisfied(l, r, f):\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if f(mid):\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return l\n",
    "        \n",
    "        peek = get_min_satisfied(0, n-2, checkpeek)\n",
    "        if marr.get(peek) < target:\n",
    "            return -1\n",
    "        \n",
    "        # 从左边去找\n",
    "        left = get_min_satisfied(0, peek, checkleft)\n",
    "        if marr.get(left) == target:\n",
    "            return left\n",
    "        \n",
    "        # 从右边找\n",
    "        right = get_min_satisfied(peek+1, n-1, checkright)\n",
    "        if marr.get(right) == target:\n",
    "            return right\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 定义一个通用的二分搜索函数，可以用于查找目标值在山脉数组中的位置\n",
    "def binary_search(mountain, target, l, r, key=lambda x: x):\n",
    "    target = key(target)  # 将目标值按照 key 函数进行转换\n",
    "    while l <= r:\n",
    "        mid = (l + r) // 2\n",
    "        cur = key(mountain.get(mid))  # 获取中间位置的值并按照 key 函数进行转换\n",
    "        if cur == target:\n",
    "            return mid  # 如果找到目标值，返回位置\n",
    "        elif cur < target:\n",
    "            l = mid + 1  # 如果当前值小于目标值，更新左边界\n",
    "        else:\n",
    "            r = mid - 1  # 如果当前值大于目标值，更新右边界\n",
    "    return -1  # 如果未找到目标值，返回 -1\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        l, r = 0, mountain_arr.length() - 1\n",
    "        \n",
    "        # 查找山脉的峰值位置\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        peak = l  # 找到山脉峰值的位置\n",
    "        \n",
    "        # 在山脉的左半部分搜索目标值\n",
    "        index = binary_search(mountain_arr, target, 0, peak)\n",
    "        if index != -1:\n",
    "            return index\n",
    "        \n",
    "        # 如果在左半部分未找到目标值，尝试在右半部分反向查找\n",
    "        index = binary_search(mountain_arr, target, peak + 1, mountain_arr.length() - 1, lambda x: -x)\n",
    "        return index\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "def binary_search(mountain, target, l, r, key=lambda x: x):\n",
    "    target = key(target)\n",
    "    while l <= r:\n",
    "        mid = (l + r) // 2\n",
    "        cur = key(mountain.get(mid))\n",
    "        if cur == target:\n",
    "            return mid\n",
    "        elif cur < target:\n",
    "            l = mid + 1\n",
    "        else:\n",
    "            r = mid - 1\n",
    "    return -1\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        l, r = 0, mountain_arr.length() - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        peak = l\n",
    "        index = binary_search(mountain_arr, target, 0, peak)\n",
    "        if index != -1:\n",
    "            return index\n",
    "        index = binary_search(mountain_arr, target, peak + 1, mountain_arr.length() - 1, lambda x: -x)\n",
    "        return index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        retVal = -1\n",
    "\n",
    "        arrSize = mountain_arr.length()\n",
    "\n",
    "        # Find the index of the peak element\n",
    "        left = 0\n",
    "        right = arrSize - 1\n",
    "        while left < right:\n",
    "            middle = left + (right - left) // 2\n",
    "            if mountain_arr.get(middle) < mountain_arr.get(middle+1):\n",
    "                left = middle + 1\n",
    "            else:\n",
    "                right = middle\n",
    "        peak = left\n",
    "\n",
    "        # Search in the strictly increasing part of the array. If found, will be returned in the loop itself.\n",
    "        left = 0\n",
    "        right = peak\n",
    "        while left <= right:\n",
    "            middle = (left + right) // 2\n",
    "            value = mountain_arr.get(middle)\n",
    "            if value == target:\n",
    "                retVal = middle\n",
    "                return retVal\n",
    "            elif value < target:\n",
    "                left = middle + 1\n",
    "            else:\n",
    "                right = middle - 1\n",
    "\n",
    "        # Search in the strictly decreasing part of the array. If found, will be returned in the loop itself.\n",
    "        left = peak + 1\n",
    "        right = arrSize - 1\n",
    "        while left <= right:\n",
    "            middle = (left + right) // 2\n",
    "            value = mountain_arr.get(middle)\n",
    "            if value == target:\n",
    "                retVal = middle\n",
    "                return retVal\n",
    "            elif value > target:\n",
    "                left = middle + 1\n",
    "            else:\n",
    "                right = middle - 1\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        def find_max(mountain_arr, N):\n",
    "\n",
    "            L, R = 0, N - 1\n",
    "\n",
    "            def check_index(index):\n",
    "                return 0 <= index <= N - 1\n",
    "\n",
    "            while L <= R:\n",
    "                mid = (L + R) // 2\n",
    "                if check_index(mid) and check_index(mid - 1) and check_index(mid + 1) \\\n",
    "                        and mountain_arr.get(mid - 1) < mountain_arr.get(mid) and mountain_arr.get(\n",
    "                    mid) > mountain_arr.get(mid + 1):\n",
    "                    return mid\n",
    "                elif check_index(mid + 1) and mountain_arr.get(mid + 1) > mountain_arr.get(mid):\n",
    "                    L = mid + 1\n",
    "                else:\n",
    "                    R = mid - 1\n",
    "            return -1\n",
    "\n",
    "        def binary_search(target, mountain_arr, left_index, right_index, key=lambda x: x):\n",
    "            while left_index <= right_index:\n",
    "                mid = (left_index + right_index) // 2\n",
    "                mid_val = key(mountain_arr.get(mid))\n",
    "                if target == mid_val:\n",
    "                    return mid\n",
    "                elif target > mid_val:\n",
    "                    left_index = mid + 1\n",
    "                else:\n",
    "                    right_index = mid - 1\n",
    "            return -1\n",
    "\n",
    "        N = mountain_arr.length()\n",
    "        max_val_index = find_max(mountain_arr, N)\n",
    "        index_ = binary_search(target, mountain_arr, 0, max_val_index)\n",
    "        if index_ == -1:\n",
    "            return binary_search(-target, mountain_arr, max_val_index, N - 1, key=lambda x: -x)\n",
    "        else:\n",
    "            return index_\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        n = mountain_arr.length()\n",
    "        l, r = 0, n - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        peak = l\n",
    "\n",
    "        idx = self.binarySearch(mountain_arr, target, 0, peak, 0)\n",
    "        if idx != -1:\n",
    "            return idx\n",
    "        else:\n",
    "            idx = self.binarySearch(mountain_arr, target, peak + 1, n - 1, 1)\n",
    "            return idx\n",
    "\n",
    "    def binarySearch(self, mountain_arr, target, l, r, sign):\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            s = mountain_arr.get(mid)\n",
    "            if s == target:\n",
    "                return mid\n",
    "            elif s < target:\n",
    "                if sign == 0:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            else:\n",
    "                if sign == 0:\n",
    "                    r = mid - 1\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def beamsearch(self, inputs, l, r, target, higher=True):\n",
    "        # l, r = 0, inputs.length()-1\n",
    "        if inputs.get(l)==target: return l\n",
    "        if inputs.get(r)==target: return r\n",
    "        mid = (l+r)//2\n",
    "        while r-l>1:\n",
    "            key = inputs.get(mid)\n",
    "            if higher: \n",
    "                if key > target:  r = mid\n",
    "                elif key < target:  l = mid\n",
    "                else:  return mid\n",
    "            else:\n",
    "                if key > target:  l = mid\n",
    "                elif key < target:  r = mid\n",
    "                else:  return mid\n",
    "            mid = (l+r)//2\n",
    "        return -1\n",
    "        \n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        l, r = 0, mountain_arr.length()-1\n",
    "        mid = (l+r)//2\n",
    "        while r-l>1:\n",
    "            # print(l, mid, r)\n",
    "            if mountain_arr.get(mid) < mountain_arr.get(mid+1):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "            mid = (l+r)//2\n",
    "        print('peak:', r)\n",
    "        peak = r\n",
    "\n",
    "        result = self.beamsearch(mountain_arr, 0, peak, target, True)\n",
    "        if result != -1:\n",
    "            return result\n",
    "        else:\n",
    "            result = self.beamsearch(mountain_arr, peak, mountain_arr.length()-1, target, False)\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        n = mountain_arr.length()\n",
    "\n",
    "        def findMax():\n",
    "            l = 0\n",
    "            r = n-1\n",
    "            res = r\n",
    "            while l <= r:\n",
    "                m = (l + r) >> 1\n",
    "                mv = mountain_arr.get(m)\n",
    "                mr = mountain_arr.get(m+1)\n",
    "                if mv < mr:\n",
    "                    l = m+1\n",
    "                else:\n",
    "                    res = m\n",
    "                    r = m-1\n",
    "            return res\n",
    "        \n",
    "        def bisearch(left, right, small2large):\n",
    "            l = left\n",
    "            r = right\n",
    "            while l <= r:\n",
    "                m = (l + r) >> 1\n",
    "                mv = mountain_arr.get(m)\n",
    "                if mv == target:\n",
    "                    return m\n",
    "                if mv > target:\n",
    "                    if small2large:\n",
    "                        r = m-1\n",
    "                    else:\n",
    "                        l = m+1\n",
    "                else:\n",
    "                    if small2large:\n",
    "                        l = m+1\n",
    "                    else:\n",
    "                        r = m-1\n",
    "            return -1\n",
    "        \n",
    "        maxPos = findMax()\n",
    "        res = bisearch(0, maxPos, True)\n",
    "        if res != -1:\n",
    "            return res\n",
    "        res = bisearch(maxPos, n-1, False)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        midIdx = self.findTopIndex(mountain_arr)\n",
    "        l, r = 0, midIdx\n",
    "\n",
    "        while l <= r:\n",
    "            m = l + (r - l) // 2\n",
    "            if mountain_arr.get(m) == target:\n",
    "                return m\n",
    "            if mountain_arr.get(m) > target:\n",
    "                r = m - 1\n",
    "            else:\n",
    "                l = m + 1\n",
    "        l, r = midIdx + 1, mountain_arr.length() - 1\n",
    "        while l <= r:\n",
    "            m = l + (r - l) // 2\n",
    "            if mountain_arr.get(m) == target:\n",
    "                return m\n",
    "            if mountain_arr.get(m) < target:\n",
    "                r = m - 1\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return -1\n",
    "\n",
    "\n",
    "    def findTopIndex(self, nums):\n",
    "        l, r = 0, nums.length() - 1\n",
    "        while l < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if nums.get(m) < nums.get(m + 1):\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m\n",
    "        return l\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        l, r = 0, mountain_arr.length() - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if mountain_arr.get(mid) > mountain_arr.get(mid+1):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        peak = l\n",
    "        l, r = 0, peak\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if mountain_arr.get(mid) >= target:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        if mountain_arr.get(l) == target:\n",
    "            return l\n",
    "        l, r = peak+1, mountain_arr.length() - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if mountain_arr.get(mid) <= target:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        if mountain_arr.get(l) == target:\n",
    "            return l\n",
    "        return -1 \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        left,right=0,mountain_arr.length()-1\n",
    "        while left<right:\n",
    "            middle=left+(right-left)//2\n",
    "            if mountain_arr.get(middle)<mountain_arr.get(middle+1):\n",
    "                left=middle+1\n",
    "            else:\n",
    "                right=middle\n",
    "        peak=left\n",
    "        def binary_search(mountain_arr:'MountainArray',target,left,right,key=lambda x:x)->int:\n",
    "            while left<=right:\n",
    "                middle=left+(right-left)//2\n",
    "                if key(mountain_arr.get(middle))==key(target):\n",
    "                    return middle\n",
    "                elif key(mountain_arr.get(middle))<key(target):\n",
    "                    left=middle+1\n",
    "                else:\n",
    "                    right=middle-1\n",
    "            return -1\n",
    "        index=binary_search(mountain_arr,target,0,peak)\n",
    "        if index!=-1:\n",
    "            return index\n",
    "        else:\n",
    "            return binary_search(mountain_arr,target,peak+1,mountain_arr.length()-1,key=lambda x:-x)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        n = mountain_arr.length()\n",
    "        l, r = 0, n - 1\n",
    "        \n",
    "        # 二分寻找山顶(162，寻找峰值)\n",
    "        while(l < r):\n",
    "            mid = (l + r + 1) >> 1\n",
    "            # 左边有序， 可以排除 0 ~ i -1\n",
    "            if mountain_arr.get(mid) > mountain_arr.get(mid - 1):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "\n",
    "        top_idx = l\n",
    "\n",
    "        # # 在左边寻找 >= target 的左边界\n",
    "        l, r = 0, top_idx\n",
    "        while(l < r):\n",
    "            mid = (l + r) >> 1\n",
    "            if mountain_arr.get(mid) >= target:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "\n",
    "        # 刚好等于 target, 直接返回\n",
    "        if (mountain_arr.get(l) == target):\n",
    "            return l\n",
    "\n",
    "        # 右边找 <= target 的左边界\n",
    "        l, r = top_idx, n - 1\n",
    "        while(l < r):\n",
    "            mid = (l + r) >> 1 \n",
    "            if mountain_arr.get(mid) <= target:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "\n",
    "        return l if mountain_arr.get(l) == target else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        n=mountain_arr.length()\n",
    "        key=lambda x:x\n",
    "        r=n-1\n",
    "        l=0\n",
    "        mid=0\n",
    "        while l<r:\n",
    "            m=(l+r)//2\n",
    "            if mountain_arr.get(m)<mountain_arr.get(m+1):\n",
    "                l=m+1\n",
    "            else:\n",
    "                r=m\n",
    "        mid=l\n",
    "        left=0\n",
    "        right=mid\n",
    "        while left<=right:\n",
    "            mm=(left+right)//2\n",
    "            cur=key(mountain_arr.get(mm))\n",
    "            if cur==target:\n",
    "                return mm\n",
    "            elif cur>target:\n",
    "                right=mm-1\n",
    "            else:\n",
    "                left=mm+1\n",
    "        ll=mid\n",
    "        rr=n-1\n",
    "        while ll<=rr:\n",
    "            mm=(ll+rr)//2\n",
    "            if mountain_arr.get(mm)==target:\n",
    "                return mm\n",
    "            elif mountain_arr.get(mm)>target:\n",
    "                ll=mm+1\n",
    "            else:\n",
    "                rr=mm-1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        n = mountain_arr.length()\n",
    "        ans = float('inf')\n",
    "\n",
    "        # 先找到山峰\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if mountain_arr.get(mid+1) > mountain_arr.get(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        partition = left\n",
    "\n",
    "        # 检查山峰左边\n",
    "        left = 0\n",
    "        right = partition\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            tmp = mountain_arr.get(mid)\n",
    "            if tmp == target:\n",
    "                return mid\n",
    "            elif tmp > target:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        if tmp == target:\n",
    "            return left\n",
    "\n",
    "        # 检查山峰右边\n",
    "        left = partition\n",
    "        right = n - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            tmp = mountain_arr.get(mid)\n",
    "            if tmp == target:\n",
    "                return mid\n",
    "            elif tmp > target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        if mountain_arr.get(left) == target:\n",
    "            return left\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "def binary_search(mountain, target, l, r, key=lambda x: x):\n",
    "    target = key(target)\n",
    "    while l <= r:\n",
    "        mid=(l+r)//2\n",
    "        cur=key(mountain.get(mid))\n",
    "        if cur==target:\n",
    "            return mid\n",
    "        elif cur<target:\n",
    "            l=mid+1\n",
    "        else:\n",
    "            r=mid-1\n",
    "    return -1\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:   \n",
    "        l, r=0, mountain_arr.length()-1\n",
    "        while l<=r:\n",
    "            mid=l+(r-l)//2\n",
    "            if mountain_arr.get(mid)<mountain_arr.get(mid+1):\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid-1\n",
    "        peak=l\n",
    "        index = binary_search(mountain_arr, target,0, peak)\n",
    "        if index!=-1:\n",
    "            return index\n",
    "        index=binary_search(mountain_arr, target, peak+1, mountain_arr.length()-1, lambda x:-x)\n",
    "        return index\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        # 找到山峰\n",
    "        left, right = 0, mountain_arr.length() - 1\n",
    "        mount_idx = 0\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            mid_val = mountain_arr.get(mid)\n",
    "            midl_val = mountain_arr.get(mid - 1)\n",
    "            midr_val = mountain_arr.get(mid + 1)\n",
    "            if midl_val < mid_val and mid_val > midr_val:\n",
    "                mount_idx = mid\n",
    "                break\n",
    "            if midl_val < midr_val:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        # 尝试在山峰左侧（递增区间）能否找到target\n",
    "        left, right = 0, mount_idx\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            mid_val = mountain_arr.get(mid)\n",
    "            if mid_val == target:\n",
    "                return mid  # 如果在该循环找不到，也就不会返回，就会进入到右侧递减区间的查找\n",
    "            elif mid_val > target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        # 尝试在山峰右侧（递减区间）能否找到target\n",
    "        left, right = mount_idx, mountain_arr.length() - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            mid_val = mountain_arr.get(mid)\n",
    "            if mid_val == target:\n",
    "                return mid\n",
    "            elif mid_val > target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return -1  # 如果在右侧递减区间也没能找到，则返回-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def binarySearchPeak(self, mountain_arr) -> int:\n",
    "        left, right = 0, mountain_arr.length() - 1\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "\n",
    "            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n",
    "    def binarySearchAscending(self, mountain_arr, left, right, target):\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if mountain_arr.get(mid) < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left if mountain_arr.get(left) == target else -1\n",
    "\n",
    "\n",
    "\n",
    "    def binarySearchDescending(self, mountain_arr, left, right, target):\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if mountain_arr.get(mid) > target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left if mountain_arr.get(left) == target else -1\n",
    "\n",
    "\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "\n",
    "        size = mountain_arr.length()\n",
    "        peek_i = self.binarySearchPeak(mountain_arr)\n",
    "        \n",
    "\n",
    "        res_left = self.binarySearchAscending(mountain_arr, 0, peek_i, target)\n",
    "\n",
    "        res_rigth = self.binarySearchDescending(mountain_arr, peek_i + 1, size - 1, target)\n",
    "\n",
    "        return res_left if res_left != -1 else res_rigth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\r\n",
    "# This is MountainArray's API interface.\r\n",
    "# You should not implement it, or speculate about its implementation\r\n",
    "# \"\"\"\r\n",
    "#class MountainArray:\r\n",
    "#    def get(self, index: int) -> int:\r\n",
    "#    def length(self) -> int:\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\r\n",
    "        n = mountain_arr.length()\r\n",
    "\r\n",
    "        l = mountain_arr.get(0)\r\n",
    "        r = mountain_arr.get(n - 1)\r\n",
    "\r\n",
    "        if l == target:\r\n",
    "            return 0\r\n",
    "        \r\n",
    "        if target < l and target < r:\r\n",
    "            return -1\r\n",
    "\r\n",
    "        def binary_search(i, j, up):\r\n",
    "            if i == j:\r\n",
    "                if target == mountain_arr.get(i):\r\n",
    "                    return i\r\n",
    "                else:\r\n",
    "                    return -1\r\n",
    "            \r\n",
    "            if i > j:\r\n",
    "                return -1\r\n",
    "\r\n",
    "            m = (i + j) // 2\r\n",
    "            a = mountain_arr.get(m)\r\n",
    "\r\n",
    "            if a == target:\r\n",
    "                return m\r\n",
    "\r\n",
    "            if up:\r\n",
    "                if a < target:\r\n",
    "                    return binary_search(m + 1, j, up)\r\n",
    "                else:\r\n",
    "                    return binary_search(i, m - 1, up)\r\n",
    "            else:\r\n",
    "                if a < target:\r\n",
    "                    return binary_search(m + 1, j, up)\r\n",
    "                else:\r\n",
    "                    return binary_search(i, m - 1, up)\r\n",
    "\r\n",
    "        def find(i, j):\r\n",
    "            print(i, j)\r\n",
    "            if i == j:\r\n",
    "                if target == mountain_arr.get(i):\r\n",
    "                    return i\r\n",
    "                else:\r\n",
    "                    return -1\r\n",
    "            if i > j:\r\n",
    "                return -1\r\n",
    "\r\n",
    "            m = (i + j) // 2\r\n",
    "            a = mountain_arr.get(m)\r\n",
    "            b = mountain_arr.get(m + 1)\r\n",
    "\r\n",
    "            if target == a:\r\n",
    "                return m\r\n",
    "\r\n",
    "            if target == b:\r\n",
    "                return m + 1\r\n",
    "\r\n",
    "            if a < b:\r\n",
    "                if target < a:\r\n",
    "                    ret = binary_search(i, m - 1, True)\r\n",
    "\r\n",
    "                    if ret != -1:\r\n",
    "                        return ret\r\n",
    "\r\n",
    "                    return find(m + 2, j)\r\n",
    "                else:\r\n",
    "                    return find(m + 2, j)\r\n",
    "\r\n",
    "            else:\r\n",
    "                if target < b:\r\n",
    "                    ret = find(i, m - 1)\r\n",
    "\r\n",
    "                    if ret != -1:\r\n",
    "                        return ret\r\n",
    "\r\n",
    "                    return binary_search(m + 2, j, False)\r\n",
    "                else:\r\n",
    "                    return find(i, m - 1)\r\n",
    "                \r\n",
    "\r\n",
    "        return find(0, n - 1)\r\n",
    "        \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        length = mountain_arr.length()\n",
    "        l, r = 1, length - 2\n",
    "\n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            left, mid, right = mountain_arr.get(m - 1), mountain_arr.get(m), mountain_arr.get(m + 1)\n",
    "            if left < mid < right:\n",
    "                l = m + 1\n",
    "            elif left > mid > right:\n",
    "                r = m - 1\n",
    "            else: \n",
    "                break\n",
    "\n",
    "        peak = m\n",
    "\n",
    "        l, r = 0, peak\n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            val = mountain_arr.get(m)\n",
    "            if val < target:\n",
    "                l = m + 1\n",
    "            elif val > target:\n",
    "                r = m - 1\n",
    "            else:\n",
    "                return m\n",
    "\n",
    "        \n",
    "        l, r = peak, length - 1\n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            val = mountain_arr.get(m)\n",
    "            if val < target:\n",
    "                r = m - 1\n",
    "            elif val > target:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                return m\n",
    "\n",
    "        return -1\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        n = mountain_arr.length()\n",
    "        def peakIndexInMountainArray(mountain_arr: 'MountainArray') -> int:\n",
    "            left, right = 0, mountain_arr.length() - 2\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if mountain_arr.get(mid) < mountain_arr.get(mid + 1):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return left\n",
    "            \n",
    "        peakIndex = peakIndexInMountainArray(mountain_arr)\n",
    "        def binary_search(mountain_arr: 'MountainArray', target: int, left: int, right: int, asc: bool) -> int:\n",
    "            target = target if asc is True else -target\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                value = mountain_arr.get(mid)\n",
    "                value = value if asc is True else -value\n",
    "                if target == value:\n",
    "                    return mid\n",
    "                elif target > value:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return -1\n",
    "\n",
    "        index = binary_search(mountain_arr, target, 0, peakIndex, True)\n",
    "        if index != -1:\n",
    "            return index\n",
    "        else:\n",
    "            return binary_search(mountain_arr, target, peakIndex + 1, n - 1, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "# class MountainArray:\n",
    "#     def __init__(self, arr):\n",
    "#         self.arr = arr\n",
    "# \n",
    "#     def get(self, index: int) -> int:\n",
    "#         return self.arr[index]\n",
    "# \n",
    "#     def length(self) -> int:\n",
    "#         return len(self.arr)\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.mn = None\n",
    "        self.length = -1\n",
    "\n",
    "    def peak(self):\n",
    "        left = 0\n",
    "        right = self.length-1\n",
    "        while left < right:\n",
    "            mid = left + (right - left)//2\n",
    "            if self.mn.get(mid) < self.mn.get(mid+1):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n",
    "    def bisect(self, left, right, target, key):\n",
    "        target = key(target)\n",
    "        while left <= right:\n",
    "            mid = left + (right - left)//2\n",
    "            cur = key(self.mn.get(mid))\n",
    "            if cur < target:\n",
    "                left = mid + 1\n",
    "            elif cur > target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                return mid\n",
    "        return -1\n",
    "\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        self.mn = mountain_arr\n",
    "        self.length = self.mn.length()\n",
    "        peak = self.peak()\n",
    "        res = self.bisect(0, peak, target, lambda x: x)\n",
    "        if res != -1:\n",
    "            return res\n",
    "        res = self.bisect(peak, self.length-1, target, lambda x: -x)\n",
    "        if res != -1:\n",
    "            return res\n",
    "        return -1\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "            # 先找到山顶的索引\n",
    "            peak_index = self.find_peak(mountain_arr)\n",
    "            \n",
    "            # 在山顶的左边查找目标值\n",
    "            left_result = self.binary_search(mountain_arr, target, 0, peak_index, lambda x: x)\n",
    "            \n",
    "            # 如果在山顶左边找到了目标值，直接返回结果\n",
    "            if left_result != -1:\n",
    "                return left_result\n",
    "            \n",
    "            # 在山顶的右边查找目标值\n",
    "            return self.binary_search(mountain_arr, target, peak_index + 1, mountain_arr.length() - 1, lambda x: -x)\n",
    "        \n",
    "    def find_peak(self, mountain_arr):\n",
    "        left, right = 0, mountain_arr.length() - 1\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "        \n",
    "    def binary_search(self, mountain_arr, target, left, right, key):\n",
    "        target *= key(1)\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            mid_val = mountain_arr.get(mid) * key(1)\n",
    "            if mid_val == target:\n",
    "                return mid\n",
    "            elif mid_val < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "def binary_search(mountain, target, l, r, key = lambda x : x):\n",
    "    target = key(target)\n",
    "    while l <= r:\n",
    "        mid = (l + r) // 2\n",
    "        cur = key(mountain.get(mid))\n",
    "        if cur == target:\n",
    "            return mid\n",
    "        elif cur < target:\n",
    "            l = mid + 1\n",
    "        else:\n",
    "            r = mid - 1\n",
    "    return -1\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "\n",
    "        l, r = 0, mountain_arr.length() - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        peak = l\n",
    "        index = binary_search(mountain_arr, target, 0, peak)\n",
    "        if index != -1:\n",
    "            return index\n",
    "        index = binary_search(mountain_arr, target, peak + 1, mountain_arr.length() - 1, lambda x : -x)\n",
    "        return index\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        n = mountain_arr.length()\n",
    "\n",
    "        def findMax():\n",
    "            l = 0\n",
    "            r = n-1\n",
    "            while l < r:\n",
    "                m = (l + r) >> 1\n",
    "                mv = mountain_arr.get(m)\n",
    "                ml = mountain_arr.get(m-1)\n",
    "                mr = mountain_arr.get(m+1)\n",
    "                if mv > ml and mv > mr:\n",
    "                    return m\n",
    "                if ml < mv:\n",
    "                    l = m\n",
    "                else:\n",
    "                    r = m\n",
    "        \n",
    "        def bisearch(left, right, small2large):\n",
    "            l = left\n",
    "            r = right\n",
    "            while l <= r:\n",
    "                m = (l + r) >> 1\n",
    "                mv = mountain_arr.get(m)\n",
    "                if mv == target:\n",
    "                    return m\n",
    "                if mv > target:\n",
    "                    if small2large:\n",
    "                        r = m-1\n",
    "                    else:\n",
    "                        l = m+1\n",
    "                else:\n",
    "                    if small2large:\n",
    "                        l = m+1\n",
    "                    else:\n",
    "                        r = m-1\n",
    "            return -1\n",
    "        \n",
    "        maxPos = findMax()\n",
    "        res = bisearch(0, maxPos, True)\n",
    "        if res != -1:\n",
    "            return res\n",
    "        res = bisearch(maxPos, n-1, False)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        n = mountain_arr.length()\n",
    "        def findmaxindex(mountain_arr):\n",
    "            n = mountain_arr.length()\n",
    "            l=0\n",
    "            r=n-1\n",
    "            while(l<r):\n",
    "                mid=(l+r)//2\n",
    "                b = mountain_arr.get(mid)\n",
    "                c = mountain_arr.get(mid+1)\n",
    "                if b<c:\n",
    "                    l=mid+1\n",
    "                else:\n",
    "                    r=mid-1\n",
    "            return l\n",
    "        peek = findmaxindex(mountain_arr)\n",
    "        l=0\n",
    "        r=peek\n",
    "        while(l<=r):\n",
    "            mid=(l+r)//2\n",
    "            a = mountain_arr.get(mid)\n",
    "            if a==target:\n",
    "                return mid\n",
    "            elif a>target:\n",
    "                r=mid-1\n",
    "            else:\n",
    "                l=mid+1\n",
    "        l=peek\n",
    "        r=n-1\n",
    "        while(l<=r):\n",
    "            mid=(l+r)//2\n",
    "            a = mountain_arr.get(mid)\n",
    "            if a==target:\n",
    "                return mid\n",
    "            elif a>target:\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid-1\n",
    "        return -1\n",
    "                     \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "def binary_search(mountain, target, l, r, key=lambda x:x):\n",
    "    target=key(target)\n",
    "    while l<=r:\n",
    "        mid=(l+r)//2\n",
    "        cur=key(mountain.get(mid))\n",
    "        if cur==target:\n",
    "            return mid\n",
    "        elif cur<target:\n",
    "            l=mid+1\n",
    "        else:\n",
    "            r=mid-1\n",
    "    return -1\n",
    "\n",
    "class Solution:\n",
    "            \n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        l=0\n",
    "        r=mountain_arr.length()-1\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if mountain_arr.get(mid)<mountain_arr.get(mid+1):\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "        peak=r\n",
    "        index=binary_search(mountain_arr,target,0,peak)\n",
    "        if index!=-1:\n",
    "            return index\n",
    "        index = binary_search(mountain_arr, target, peak + 1, mountain_arr.length() - 1, lambda x: -x)\n",
    "        return index\n",
    "        \n",
    "     \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        N = mountain_arr.length()\n",
    "\n",
    "        def findMountainPeak():\n",
    "            lo, hi = 0, N - 1\n",
    "            while lo < hi:\n",
    "                mid = (lo + hi) // 2\n",
    "                mid_val = mountain_arr.get(mid)\n",
    "                mid_next_val = mountain_arr.get(mid + 1)\n",
    "                if mid_val < mid_next_val:\n",
    "                    lo = mid + 1\n",
    "                else:\n",
    "                    hi = mid\n",
    "            return lo\n",
    "        \n",
    "        def binarySearch(lo: int, hi: int, target: int, key_func) -> int:\n",
    "            target_val = key_func(target)\n",
    "            while lo <= hi:\n",
    "                mid = (lo + hi) // 2\n",
    "                mid_val = key_func(mountain_arr.get(mid))\n",
    "                if mid_val == target_val:\n",
    "                    return mid\n",
    "                elif mid_val < target_val:\n",
    "                    lo = mid + 1\n",
    "                else:\n",
    "                    hi = mid - 1\n",
    "            return -1\n",
    "\n",
    "        peak = findMountainPeak()\n",
    "        target_idx = binarySearch(0, peak, target, lambda x: x)\n",
    "        if target_idx != -1:\n",
    "            return target_idx\n",
    "        else:\n",
    "            return binarySearch(peak + 1, N - 1, target, lambda x: -x)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "            # 先找到山顶的索引\n",
    "            peak_index = self.find_peak(mountain_arr)\n",
    "            \n",
    "            # 在山顶的左边查找目标值\n",
    "            left_result = self.binary_search(mountain_arr, target, 0, peak_index, lambda x: x)\n",
    "            \n",
    "            # 如果在山顶左边找到了目标值，直接返回结果\n",
    "            if left_result != -1:\n",
    "                return left_result\n",
    "            \n",
    "            # 在山顶的右边查找目标值\n",
    "            return self.binary_search(mountain_arr, target, peak_index + 1, mountain_arr.length() - 1, lambda x: -x)\n",
    "        \n",
    "    def find_peak(self, mountain_arr):\n",
    "        left, right = 0, mountain_arr.length() - 1\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "        \n",
    "    def binary_search(self, mountain_arr, target, left, right, key):\n",
    "        target *= key(1)\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            mid_val = mountain_arr.get(mid) * key(1)\n",
    "            if mid_val == target:\n",
    "                return mid\n",
    "            elif mid_val < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "def binary_find(l,r,mountain_arr,target,key = lambda x:x):\n",
    "        target = key(target)\n",
    "        while l <= r:\n",
    "            mid = (l+r)//2\n",
    "            v = key(mountain_arr.get(mid))\n",
    "            if v == target:\n",
    "                return mid\n",
    "            elif v > target:\n",
    "                r = mid-1\n",
    "            else:\n",
    "                l = mid+1\n",
    "        return -1\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        # 找峰顶\n",
    "        L = mountain_arr.length()\n",
    "        l,r = 0,L-1\n",
    "        peak = -1\n",
    "        while l <= r:\n",
    "            mid = (l+r)//2\n",
    "            if mountain_arr.get(mid) > mountain_arr.get(mid+1):\n",
    "                peak = mid\n",
    "                r = mid-1\n",
    "            else:\n",
    "                l = mid+1\n",
    "        peakv = mountain_arr.get(peak)\n",
    "        if peakv == target:return peak\n",
    "        if peakv < target:return -1\n",
    "        # 左\n",
    "        index = binary_find(0,peak-1,mountain_arr,target)\n",
    "        if index!= -1:\n",
    "            return index \n",
    "        # 右\n",
    "        return binary_find(peak+1,L-1,mountain_arr,target,lambda x:-x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        n = mountain_arr.length()\n",
    "\n",
    "        # find the peak\n",
    "        low = 0\n",
    "        high = n - 1\n",
    "\n",
    "        while low < high:\n",
    "            mid = (low + high) // 2\n",
    "            mid_val = mountain_arr.get(mid)\n",
    "            mid_next_val = mountain_arr.get(mid + 1)\n",
    "\n",
    "            if mid_val < mid_next_val:\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid\n",
    "\n",
    "        peak_idx = low\n",
    "\n",
    "        # get the values for comparison\n",
    "        peak_val = mountain_arr.get(peak_idx)\n",
    "\n",
    "        # search the left side\n",
    "        low = 0\n",
    "        high = peak_idx\n",
    "\n",
    "        while low < high:\n",
    "            mid = (low + high) // 2\n",
    "            mid_val = mountain_arr.get(mid)\n",
    "\n",
    "            if mid_val < target:\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid\n",
    "\n",
    "        if mountain_arr.get(low) == target:\n",
    "            return low\n",
    "\n",
    "        # search the right side\n",
    "        low = peak_idx + 1\n",
    "        high = n - 1\n",
    "\n",
    "        while low < high:\n",
    "            mid = (low + high) // 2\n",
    "            mid_val = mountain_arr.get(mid)\n",
    "\n",
    "            if mid_val > target:\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid\n",
    "\n",
    "        if mountain_arr.get(low) == target:\n",
    "            return low\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\r\n",
    "# This is MountainArray's API interface.\r\n",
    "# You should not implement it, or speculate about its implementation\r\n",
    "# \"\"\"\r\n",
    "class Solution:\r\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\r\n",
    "        # 1. 找到山峰\r\n",
    "        left, right = 0, mountain_arr.length() - 1\r\n",
    "        peak_idx = 0\r\n",
    "        while left <= right:\r\n",
    "            mid = (left + right) // 2\r\n",
    "            mid_val = mountain_arr.get(mid)\r\n",
    "            midl_val = mountain_arr.get(mid - 1)\r\n",
    "            midr_val = mountain_arr.get(mid + 1)\r\n",
    "            if midl_val < mid_val and mid_val > midr_val: # 找到山峰\r\n",
    "                peak_idx = mid\r\n",
    "                break\r\n",
    "            if midl_val < midr_val: # 山峰在右邊\r\n",
    "                left = mid\r\n",
    "            else: # 山峰在左邊\r\n",
    "                right = mid\r\n",
    "        # 2. 在山峰左側(遞增區間)找target\r\n",
    "        left, right = 0, peak_idx\r\n",
    "        while left <= right:\r\n",
    "            mid = (left + right) // 2\r\n",
    "            mid_val = mountain_arr.get(mid)\r\n",
    "            if mid_val == target:\r\n",
    "                return mid  # 在左側找到\r\n",
    "            elif mid_val > target:\r\n",
    "                right = mid - 1\r\n",
    "            else:\r\n",
    "                left = mid + 1\r\n",
    "        # 3. 在山峰右側(遞減區間)找target\r\n",
    "        left, right = peak_idx, mountain_arr.length() - 1\r\n",
    "        while left <= right:\r\n",
    "            mid = (left + right) // 2\r\n",
    "            mid_val = mountain_arr.get(mid)\r\n",
    "            if mid_val == target:\r\n",
    "                return mid  # 在右側找到\r\n",
    "            elif mid_val > target:\r\n",
    "                left = mid + 1\r\n",
    "            else:\r\n",
    "                right = mid - 1\r\n",
    "        return -1 # 沒找到"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        n = mountain_arr.length()\n",
    "\n",
    "        # Function for binary search\n",
    "        def binary_search(low, high, is_increasing):\n",
    "            while low < high:\n",
    "                mid = (low + high) // 2\n",
    "                mid_val = mountain_arr.get(mid)\n",
    "\n",
    "                if is_increasing:\n",
    "                    if mid_val < target:\n",
    "                        low = mid + 1\n",
    "                    else:\n",
    "                        high = mid\n",
    "                else:\n",
    "                    if mid_val > target:\n",
    "                        low = mid + 1\n",
    "                    else:\n",
    "                        high = mid\n",
    "            return low\n",
    "\n",
    "        # find the peak\n",
    "        low, high, peak_idx = 0, n - 1, 0\n",
    "\n",
    "        while low < high:\n",
    "            mid = (low + high) // 2\n",
    "            mid_val = mountain_arr.get(mid)\n",
    "            mid_next_val = mountain_arr.get(mid + 1)\n",
    "\n",
    "            if mid_val < mid_next_val:\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid\n",
    "\n",
    "        peak_idx = low\n",
    "        \n",
    "        left_result = binary_search(0, peak_idx, True)\n",
    "        if mountain_arr.get(left_result) == target:\n",
    "            return left_result\n",
    "\n",
    "\n",
    "        right_result = binary_search(peak_idx+1, n - 1, False)\n",
    "        if mountain_arr.get(right_result) == target:\n",
    "            return right_result\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        sz = mountain_arr.length()\n",
    "        i = bisect_left(range(sz-1), True, key=lambda x: mountain_arr.get(x) > mountain_arr.get(x+1))\n",
    "        assert 0 < i < sz - 1, (i, sz)\n",
    "        peek = mountain_arr.get(i)\n",
    "        lval, rval = mountain_arr.get(0), mountain_arr.get(sz-1)\n",
    "        assert lval < peek and rval < peek, (lval, peek, rval, i, sz)\n",
    "        if lval <= target <= peek:\n",
    "            k = bisect_left(range(i+1), target, key=lambda x: mountain_arr.get(x))\n",
    "            if mountain_arr.get(k) == target:\n",
    "                return k\n",
    "        if rval <= target <= peek:\n",
    "            k = bisect_left(range(i, sz), -target, key=lambda x: -mountain_arr.get(x))\n",
    "            if mountain_arr.get(i+k) == target:\n",
    "                return i+k\n",
    "        return -1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        n = mountain_arr.length()\n",
    "\n",
    "        low = 0\n",
    "        high = n - 1\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        ceil = high if mountain_arr.get(high) > mountain_arr.get(low) else low\n",
    "\n",
    "        low = 0\n",
    "        high = ceil\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if mountain_arr.get(mid) < target:\n",
    "                low = mid\n",
    "            elif mountain_arr.get(mid) > target:\n",
    "                high = mid\n",
    "            else:\n",
    "                return mid\n",
    "        if mountain_arr.get(low) == target:\n",
    "            return low\n",
    "        if mountain_arr.get(high) == target:\n",
    "            return high\n",
    "\n",
    "        low = ceil\n",
    "        high = n - 1\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if mountain_arr.get(mid) > target:\n",
    "                low = mid\n",
    "            elif mountain_arr.get(mid) < target:\n",
    "                high = mid\n",
    "            else:\n",
    "                return mid\n",
    "\n",
    "        if mountain_arr.get(low) == target:\n",
    "            return low\n",
    "        if mountain_arr.get(high) == target:\n",
    "            return high\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "def binary_find(l,r,mountain_arr,target,key = lambda x:x):\n",
    "        target = key(target)\n",
    "        while l <= r:\n",
    "            mid = (l+r)//2\n",
    "            v = key(mountain_arr.get(mid))\n",
    "            if v == target:\n",
    "                return mid\n",
    "            elif v > target:\n",
    "                r = mid-1\n",
    "            else:\n",
    "                l = mid+1\n",
    "        return -1\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        # 找峰顶\n",
    "        L = mountain_arr.length()\n",
    "        l,r = 0,L-1\n",
    "        peak = -1\n",
    "        while l <= r:\n",
    "            mid = (l+r)//2\n",
    "            if mountain_arr.get(mid) > mountain_arr.get(mid+1):\n",
    "                peak = mid\n",
    "                r = mid-1\n",
    "            else:\n",
    "                l = mid+1\n",
    "        peakv = mountain_arr.get(peak)\n",
    "        if peakv == target:return peak\n",
    "        if peakv < target:return -1\n",
    "        # 左\n",
    "        index = binary_find(0,peak-1,mountain_arr,target)\n",
    "        if index!= -1:\n",
    "            return index \n",
    "        # 右\n",
    "        return binary_find(peak+1,L-1,mountain_arr,target,lambda x:-x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "def binary_search(mountain, target, l, r, key=lambda x:x):\n",
    "    target=key(target)\n",
    "    while l<=r:\n",
    "        mid=(l+r)//2\n",
    "        cur=key(mountain.get(mid))\n",
    "        if cur==target:\n",
    "            return mid\n",
    "        elif cur<target:\n",
    "            l=mid+1\n",
    "        else:\n",
    "            r=mid-1\n",
    "    return -1\n",
    "    \n",
    "    \n",
    "    \n",
    "\n",
    "class Solution:\n",
    "            \n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        l=0\n",
    "        r=mountain_arr.length()-1\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if mountain_arr.get(mid)<mountain_arr.get(mid+1):\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "        peak=r\n",
    "        index=binary_search(mountain_arr,target,0,peak)\n",
    "        if index!=-1:\n",
    "            return index\n",
    "        index = binary_search(mountain_arr, target, peak+1 , mountain_arr.length() - 1, lambda x: -x)\n",
    "        return index\n",
    "        \n",
    "     \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "def binary_search(mountain, target, l, r, key=lambda x: x):\n",
    "    target = key(target)\n",
    "    while l <= r:\n",
    "        mid = (l + r) // 2\n",
    "        cur = key(mountain.get(mid))\n",
    "        if cur == target:\n",
    "            return mid\n",
    "        elif cur < target:\n",
    "            l = mid + 1\n",
    "        else:\n",
    "            r = mid - 1\n",
    "    return -1\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        l, r = 0, mountain_arr.length() - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        peak = l \n",
    "        index = binary_search(mountain_arr, target, 0, peak)\n",
    "        if index != - 1:\n",
    "            return index\n",
    "        index = binary_search(mountain_arr, target, peak + 1, mountain_arr.length() - 1, lambda x: -x)\n",
    "        return index\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        n = mountain_arr.length()\n",
    "\n",
    "        low = 0\n",
    "        high = n - 1\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        ceil = high if mountain_arr.get(high) > mountain_arr.get(low) else low\n",
    "\n",
    "        low = 0\n",
    "        high = ceil\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if mountain_arr.get(mid) < target:\n",
    "                low = mid\n",
    "            elif mountain_arr.get(mid) > target:\n",
    "                high = mid\n",
    "            else:\n",
    "                return mid\n",
    "        if mountain_arr.get(low) == target:\n",
    "            return low\n",
    "        if mountain_arr.get(high) == target:\n",
    "            return high\n",
    "\n",
    "        low = ceil\n",
    "        high = n - 1\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if mountain_arr.get(mid) > target:\n",
    "                low = mid\n",
    "            elif mountain_arr.get(mid) < target:\n",
    "                high = mid\n",
    "            else:\n",
    "                return mid\n",
    "\n",
    "        if mountain_arr.get(low) == target:\n",
    "            return low\n",
    "        if mountain_arr.get(high) == target:\n",
    "            return high\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        \n",
    "        n = mountain_arr.length()\n",
    "        i, j = 0, n-1\n",
    "        while i < j-1:\n",
    "            mid = i+(j-i)//2\n",
    "            x, y = mountain_arr.get(mid), mountain_arr.get(mid+1)\n",
    "            if x < y:\n",
    "                i = mid+1\n",
    "            else:\n",
    "                j = mid-1\n",
    "        ceil = i if mountain_arr.get(i) > mountain_arr.get(j) else j\n",
    "\n",
    "        i, j = 0, ceil\n",
    "        while i < j-1:\n",
    "            mid = i + (j - i) // 2\n",
    "            x = mountain_arr.get(mid)\n",
    "            if x < target:\n",
    "                i = mid + 1\n",
    "            elif x > target:\n",
    "                j = mid - 1\n",
    "            else:\n",
    "                return mid\n",
    "        if mountain_arr.get(i) == target:\n",
    "            return i\n",
    "        if mountain_arr.get(j) == target:\n",
    "            return j\n",
    "\n",
    "        i, j = ceil, n-1\n",
    "        while i < j - 1:\n",
    "            mid = i + (j - i) // 2\n",
    "            x = mountain_arr.get(mid)\n",
    "            if x > target:\n",
    "                i = mid + 1\n",
    "            elif x < target:\n",
    "                j = mid - 1\n",
    "            else:\n",
    "                return mid\n",
    "        if mountain_arr.get(i) == target:\n",
    "            return i\n",
    "        if mountain_arr.get(j) == target:\n",
    "            return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "\n",
    "\n",
    "        n = mountain_arr.length()\n",
    "        ans = []\n",
    "\n",
    "        low, high =0, n-1\n",
    "\n",
    "        while low<high:\n",
    "            mid = (low+high)//2\n",
    "            val = mountain_arr.get(mid)\n",
    "            next_val = mountain_arr.get(mid+1)\n",
    "            if val>next_val:\n",
    "                high = mid\n",
    "            elif val<next_val:\n",
    "                low = mid+1\n",
    "        \n",
    "        #print(low,\"low\")\n",
    "        index = low \n",
    "        left,right = 0,low-1\n",
    "        ans = []\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            val = mountain_arr.get(mid)\n",
    "            if val == target:\n",
    "                ans.append(mid)\n",
    "                break\n",
    "            elif val>target:\n",
    "                right = mid-1\n",
    "            elif val<target:\n",
    "                left = mid+1\n",
    "        \n",
    "\n",
    "\n",
    "        left,right = low,n-1\n",
    "        #print(left,right)\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            val = mountain_arr.get(mid)\n",
    "            if val == target:\n",
    "                ans.append(mid)\n",
    "                break\n",
    "            elif val>target:\n",
    "                left = mid+1\n",
    "            elif val<target:\n",
    "                right = mid-1\n",
    "\n",
    "        if not ans:\n",
    "            return -1 \n",
    "        else:\n",
    "            return min(ans)\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        \n",
    "        def find_peak(lo,hi):\n",
    "            while lo<hi:\n",
    "                mid = (lo+hi)>>1\n",
    "                m = mountain_arr.get(mid)\n",
    "                if m>mountain_arr.get(mid+1):\n",
    "                    hi = mid-1\n",
    "                else:\n",
    "                    lo = mid+1\n",
    "            return lo\n",
    "\n",
    "        def find_left(l,r):\n",
    "            while l<=r:\n",
    "                mid = (l+r)>>1\n",
    "                m = mountain_arr.get(mid)\n",
    "                if m==target:\n",
    "                    return mid\n",
    "                elif m<target:\n",
    "                    l = mid+1\n",
    "                else:\n",
    "                    r = mid-1\n",
    "            return -1\n",
    "\n",
    "        def find_right(l,r):\n",
    "            while l<=r:\n",
    "                mid = (l+r)>>1\n",
    "                m = mountain_arr.get(mid)\n",
    "                if m == target:\n",
    "                    return mid\n",
    "                elif m<target:\n",
    "                    r = mid-1\n",
    "                else:\n",
    "                    l = mid+1\n",
    "            return -1\n",
    "                \n",
    "        L = mountain_arr.length()\n",
    "        peak = find_peak(1,L-2)\n",
    "        \n",
    "        if mountain_arr.get(peak) == target:\n",
    "            return peak\n",
    "        else:\n",
    "            l = find_left(0,peak-1)\n",
    "            r = find_right(peak+1,L-1)\n",
    "            return max(l,r) if (m:=min(l,r))==-1 else m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\r\n",
    "# This is MountainArray's API interface.\r\n",
    "# You should not implement it, or speculate about its implementation\r\n",
    "# \"\"\"\r\n",
    "#class MountainArray:\r\n",
    "#    def get(self, index: int) -> int:\r\n",
    "#    def length(self) -> int:\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\r\n",
    "        start, end = 0, mountain_arr.length() - 1\r\n",
    "        while True:\r\n",
    "            mid = (start + end) // 2\r\n",
    "            pred = mountain_arr.get(mid - 1) if mid > 0 else -1\r\n",
    "            curr = mountain_arr.get(mid)\r\n",
    "            next = mountain_arr.get(mid + 1) if mid < mountain_arr.length() else -1\r\n",
    "            if pred < curr and curr > next:\r\n",
    "                break\r\n",
    "            elif pred < curr and curr < next:\r\n",
    "                start = mid + 1\r\n",
    "            elif pred > curr and curr > next:\r\n",
    "                end = mid - 1\r\n",
    "        peak = mid\r\n",
    "\r\n",
    "        start, end = 0, peak\r\n",
    "        while start <= end:\r\n",
    "            mid = (start + end) // 2\r\n",
    "            curr = mountain_arr.get(mid)\r\n",
    "            if curr == target:\r\n",
    "                return mid\r\n",
    "            elif curr < target:\r\n",
    "                start = mid + 1\r\n",
    "            else:\r\n",
    "                end = mid - 1\r\n",
    "        \r\n",
    "        start, end = peak, mountain_arr.length() - 1\r\n",
    "        while start <= end:\r\n",
    "            mid = (start + end) // 2\r\n",
    "            curr = mountain_arr.get(mid)\r\n",
    "            if curr == target:\r\n",
    "                return mid\r\n",
    "            elif curr > target:\r\n",
    "                start = mid + 1\r\n",
    "            else:\r\n",
    "                end = mid - 1\r\n",
    "        return -1\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "def binary_search(mountain, target, l, r, key=lambda x:x):\n",
    "    target=key(target)\n",
    "    while l<r:\n",
    "        mid=(l+r)//2\n",
    "        cur=key(mountain.get(mid))\n",
    "        if cur<target:\n",
    "            l=mid+1\n",
    "        else:\n",
    "            r=mid\n",
    "    if key(mountain.get(r))==target:\n",
    "        return r\n",
    "    else:\n",
    "        return -1\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "\n",
    "class Solution:\n",
    "            \n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        l=0\n",
    "        r=mountain_arr.length()-1\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if mountain_arr.get(mid)<mountain_arr.get(mid+1):\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "        peak=r\n",
    "        index=binary_search(mountain_arr,target,0,peak)\n",
    "        if index!=-1:\n",
    "            return index\n",
    "        else:\n",
    "            index = binary_search(mountain_arr, target, peak+1, mountain_arr.length() - 1, lambda x: -x)\n",
    "            return index\n",
    "        \n",
    "     \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        l = 0\n",
    "        r = mountain_arr.length() - 1\n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            a = -1 if m - 1 < 0 else mountain_arr.get(m - 1)\n",
    "            b = mountain_arr.get(m)\n",
    "            c = inf if m + 1 >= mountain_arr.length() else mountain_arr.get(m + 1)\n",
    "            if a < b < c:\n",
    "                l = m + 1\n",
    "            elif a < b > c:\n",
    "                break\n",
    "            elif a > b > c:\n",
    "                r = m - 1\n",
    "        peak_idx = m\n",
    "\n",
    "        l = 0\n",
    "        r = peak_idx\n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            if mountain_arr.get(m) < target:\n",
    "                l = m + 1\n",
    "            elif mountain_arr.get(m) > target:\n",
    "                r = m - 1\n",
    "            else:\n",
    "                return m\n",
    "\n",
    "        l = peak_idx\n",
    "        r = mountain_arr.length() - 1\n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            if mountain_arr.get(m) < target:\n",
    "                r = m - 1\n",
    "            elif mountain_arr.get(m) > target:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                return m\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "def binary_find(l,r,mountain_arr,target,key = lambda x:x):\n",
    "        target = key(target)\n",
    "        while l <= r:\n",
    "            mid = (l+r)//2\n",
    "            v = key(mountain_arr.get(mid))\n",
    "            if v == target:\n",
    "                return mid\n",
    "            elif v < target:\n",
    "                l = mid+1\n",
    "            else:\n",
    "                r = mid-1\n",
    "        return -1\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        # 找峰顶\n",
    "        L = mountain_arr.length()\n",
    "        l,r = 0,L-1\n",
    "        peak = -1\n",
    "        while l <= r:\n",
    "            mid = (l+r)//2\n",
    "            if mountain_arr.get(mid) > mountain_arr.get(mid+1):\n",
    "                peak = mid\n",
    "                r = mid-1\n",
    "            else:\n",
    "                l = mid+1\n",
    "        peakv = mountain_arr.get(peak)\n",
    "        if peakv == target:return peak\n",
    "        if peakv < target:return -1\n",
    "        # 左\n",
    "        index = binary_find(0,peak-1,mountain_arr,target)\n",
    "        if index!= -1:\n",
    "            return index \n",
    "        # 右\n",
    "        return binary_find(peak+1,L-1,mountain_arr,target,lambda x:-x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "def binary_search(mountain, target, l, r, key=lambda x: x):\n",
    "    target = key(target)\n",
    "    while l <= r:\n",
    "        mid = (l + r) // 2\n",
    "        cur = key(mountain.get(mid))   ##当前索引\n",
    "        if cur == target:\n",
    "            return mid\n",
    "        elif cur < target:\n",
    "            l = mid + 1\n",
    "        else:\n",
    "            r = mid - 1\n",
    "    return -1\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        l, r = 0, mountain_arr.length() - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        peak = l\n",
    "        index = binary_search(mountain_arr, target, 0, peak)\n",
    "        if index != -1:\n",
    "            return index\n",
    "        index = binary_search(mountain_arr, target, peak + 1, mountain_arr.length() - 1, lambda x: -x)\n",
    "        return index\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        l, r = 0, mountain_arr.length() - 1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        peak = l\n",
    "\n",
    "        l, r = 0, peak\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if mountain_arr.get(mid) == target:\n",
    "                return mid\n",
    "            elif mountain_arr.get(mid) < target:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        \n",
    "        l, r = peak + 1, mountain_arr.length() - 1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if mountain_arr.get(mid) == target:\n",
    "                return mid\n",
    "            elif mountain_arr.get(mid) < target:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        \n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def binary_search(self,arr:'MountainArray',target:int,l:int,r:int,key = lambda x:x) -> int: \n",
    "        target = key(target)\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            cur = key(arr.get(mid))\n",
    "            if cur == target:\n",
    "                return mid\n",
    "            elif cur < target:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return -1\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        n = mountain_arr.length()\n",
    "        left,right = 0,n - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        peak = left\n",
    "        index = self.binary_search(mountain_arr,target,0,peak)\n",
    "        if index != -1:\n",
    "            return index\n",
    "        index = self.binary_search(mountain_arr,target,peak + 1,n-1,lambda x:-x)\n",
    "        return index\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        n = mountain_arr.length()\n",
    "        peak_i = self.binarySearchPeak(mountain_arr, n)\n",
    "        if mountain_arr.get(peak_i) == target:\n",
    "            return peak_i\n",
    "        res_left = self.binarySearchAscending(mountain_arr, 0, peak_i-1, target)\n",
    "        res_right = self.binarySearchDescending(mountain_arr, peak_i+1, n-1, target)\n",
    "        return res_left if res_left >= 0 else res_right\n",
    "    def binarySearchPeak(self, mountain_arr: 'MountainArray', n: int) -> int:\n",
    "        left, right = 0, n-1\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if mountain_arr.get(mid) < mountain_arr.get(mid+1):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "    def binarySearchAscending(self, mountain_arr: 'MountainArray', left: int, right: int, target: int) -> int:\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            mid_val = mountain_arr.get(mid)\n",
    "            if mid_val == target:\n",
    "                return mid\n",
    "            elif mid_val < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return -1\n",
    "    def binarySearchDescending(self,  mountain_arr: 'MountainArray', left: int, right: int, target: int) -> int:\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            mid_val = mountain_arr.get(mid)\n",
    "            if mid_val == target:\n",
    "                return mid\n",
    "            elif mid_val < target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        def binary_search(l,r,target,key=lambda x:x):#默认key=lambda x:x\n",
    "            target = key(target)\n",
    "            while(l<=r):\n",
    "                mid = l + (r-l)//2\n",
    "                cur = key(mountain_arr.get(mid))\n",
    "                if target == cur:\n",
    "                    return mid\n",
    "                elif cur >target:\n",
    "                    r = mid-1\n",
    "                else:\n",
    "                    l = mid+1\n",
    "            return -1 #表示没找到\n",
    "        #先找峰值\n",
    "        n = mountain_arr.length()\n",
    "        l,r = 0,n-1\n",
    "        while l<r:#左闭右开\n",
    "            mid = l + (r-l)//2\n",
    "            if mountain_arr.get(mid)<mountain_arr.get(mid+1):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "\n",
    "        peek = l #峰值，此时l==r\n",
    "\n",
    "        index = binary_search(0,peek,target)\n",
    "        if index == -1:\n",
    "            index = binary_search(peek,n-1,target,key = lambda x:-x)\n",
    "\n",
    "        return index\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        #在左边查询，如果查询到，则直接返回\n",
    "\n",
    "        #在右边查找，"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        # 二分查找山峰\n",
    "        # 山峰左边（递增）二分查找target\n",
    "        # 山峰右边（递减）二分查找target\n",
    "        left = 0\n",
    "        right = mountain_arr.length() - 1\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if mountain_arr.get(mid) > mountain_arr.get(mid+1):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        peak = right\n",
    "\n",
    "        left = 0\n",
    "        right = peak\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if mountain_arr.get(mid) == target:\n",
    "                return mid\n",
    "            elif mountain_arr.get(mid) > target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        left = peak\n",
    "        right = mountain_arr.length() - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if mountain_arr.get(mid) == target:\n",
    "                return mid\n",
    "            elif mountain_arr.get(mid) > target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "\n",
    "        n = mountain_arr.length()\n",
    "        left, right = 0, n-1\n",
    "        if mountain_arr.get(left) == target:\n",
    "            return left\n",
    "\n",
    "        # find peak\n",
    "        peak = 0\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            a, b, c = mountain_arr.get(mid-1), mountain_arr.get(mid), mountain_arr.get(mid+1)\n",
    "            if b > a and b > c:\n",
    "                if b == target:\n",
    "                    return mid\n",
    "                peak = mid\n",
    "                break\n",
    "            elif b > a and b < c:\n",
    "                left = mid + 1\n",
    "            elif b < a and b > c:\n",
    "                right = mid\n",
    "                \n",
    "        def find_target_increase(target, left, right):\n",
    "            if mountain_arr.get(left) == target:\n",
    "                return left\n",
    "            if mountain_arr.get(right) == target:\n",
    "                return right\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                val = mountain_arr.get(mid)\n",
    "                if val == target:\n",
    "                    return mid\n",
    "                elif val < target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return -1\n",
    "\n",
    "        def find_target_decrease(target, left, right):\n",
    "            if mountain_arr.get(left) == target:\n",
    "                return left\n",
    "            if mountain_arr.get(right) == target:\n",
    "                return right\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                val = mountain_arr.get(mid)\n",
    "                if val == target:\n",
    "                    return mid\n",
    "                elif val > target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return -1\n",
    "            \n",
    "        left_res, right_res = find_target_increase(target, 0, peak), find_target_decrease(target, peak, n-1)\n",
    "        if left_res != -1:\n",
    "            return left_res\n",
    "        elif right_res != -1:\n",
    "            return right_res\n",
    "        return -1\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        def binary_search_peak(arr):\n",
    "            left, right = 0, arr.length()-1\n",
    "            while left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if arr.get(mid) < arr.get(mid + 1):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return left\n",
    "\n",
    "        def binary_search_ascend(arr, left, right, target):\n",
    "            while left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if arr.get(mid) < target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return left if arr.get(left) == target else -1\n",
    "\n",
    "        def binary_search_descend(arr, left, right, target):\n",
    "            while left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if arr.get(mid) > target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return left if arr.get(left) == target else -1\n",
    "\n",
    "        size = mountain_arr.length()\n",
    "        peek = binary_search_peak(mountain_arr)\n",
    "        left = binary_search_ascend(mountain_arr, 0, peek, target)\n",
    "        right = binary_search_descend(mountain_arr, peek + 1, size - 1, target)\n",
    "        return left if left != -1 else right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        # MountainArray.get 的调用不能超过100次，所以肯定是二分解决问题的\n",
    "        # 山脉数组的情况应该是比较特殊的，可以先找出山峰，然后两次二分\n",
    "        # 比较相邻的位置是可以找出山峰的\n",
    "        n = mountain_arr.length()\n",
    "        \n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if mountain_arr.get(mid) > mountain_arr.get(mid+1):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        # 找出山峰之后可以拆成两部分 [0, left], [left+1, n-1]\n",
    "        l1 = 0\n",
    "        r1 = left\n",
    "        while l1 <= r1:\n",
    "            mid = (l1+r1) // 2\n",
    "            mid_val = mountain_arr.get(mid)\n",
    "            if mid_val < target:\n",
    "                l1 = mid + 1\n",
    "            elif mid_val > target:\n",
    "                r1 = mid - 1\n",
    "            else:\n",
    "                return mid\n",
    "        \n",
    "        l1 = left + 1\n",
    "        r1 = n - 1\n",
    "        while l1 <= r1:\n",
    "            mid = (l1+r1) // 2\n",
    "            mid_val = -mountain_arr.get(mid)\n",
    "            if mid_val < -target:\n",
    "                l1 = mid + 1\n",
    "            elif mid_val > -target:\n",
    "                r1 = mid - 1\n",
    "            else:\n",
    "                return mid\n",
    "        \n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "# class Solution:\n",
    "    # def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "    #     n = mountain_arr.length()\n",
    "    #     peak_i = self.binarySearchPeak(mountain_arr, n)\n",
    "    #     if mountain_arr.get(peak_i) == target:\n",
    "    #         return peak_i\n",
    "    #     res_left = self.binarySearchAscending(mountain_arr, 0, peak_i-1, target)\n",
    "    #     res_right = self.binarySearchDescending(mountain_arr, peak_i+1, n-1, target)\n",
    "    #     return res_left if res_left >= 0 else res_right\n",
    "    # def binarySearchPeak(self, mountain_arr: 'MountainArray', n: int) -> int:\n",
    "    #     left, right = 0, n-1\n",
    "    #     while left < right:\n",
    "    #         mid = left + (right - left) // 2\n",
    "    #         if mountain_arr.get(mid) < mountain_arr.get(mid+1):\n",
    "    #             left = mid\n",
    "    #         else:\n",
    "    #             right = mid - 1\n",
    "    #     return left\n",
    "    # def binarySearchAscending(self, mountain_arr: 'MountainArray', left: int, right: int, target: int) -> int:\n",
    "    #     while left <= right:\n",
    "    #         mid = left + (right - left) // 2\n",
    "    #         mid_val = mountain_arr.get(mid)\n",
    "    #         if mid_val == target:\n",
    "    #             return mid\n",
    "    #         elif mid_val < target:\n",
    "    #             left = mid + 1\n",
    "    #         else:\n",
    "    #             right = mid - 1\n",
    "    #     return -1\n",
    "    # def binarySearchDescending(self,  mountain_arr: 'MountainArray', left: int, right: int, target: int) -> int:\n",
    "    #     while left <= right:\n",
    "    #         mid = left + (right - left) // 2\n",
    "    #         mid_val = mountain_arr.get(mid)\n",
    "    #         if mid_val == target:\n",
    "    #             return mid\n",
    "    #         elif mid_val < target:\n",
    "    #             right = mid - 1\n",
    "    #         else:\n",
    "    #             left = mid + 1\n",
    "    #     return -1\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def binarySearchPeak(self, mountain_arr) -> int:\n",
    "        left, right = 0, mountain_arr.length() - 1\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n",
    "    def binarySearchAscending(self, mountain_arr, left, right, target):\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if mountain_arr.get(mid) < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left if mountain_arr.get(left) == target else -1\n",
    "\n",
    "    def binarySearchDescending(self, mountain_arr, left, right, target):\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if mountain_arr.get(mid) > target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left if mountain_arr.get(left) == target else -1\n",
    "\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        size = mountain_arr.length()\n",
    "        peek_i = self.binarySearchPeak(mountain_arr)\n",
    "\n",
    "        res_left = self.binarySearchAscending(mountain_arr, 0, peek_i, target)\n",
    "        res_right = self.binarySearchDescending(mountain_arr, peek_i + 1, size - 1, target)\n",
    "        \n",
    "        return res_left if res_left != -1 else res_right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        n = mountain_arr.length()\n",
    "        def find_left():\n",
    "            left, right = 0, n - 1\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                a = mountain_arr.get(mid)\n",
    "                if (mid == 0 or mountain_arr.get(mid - 1) < a) and a == target:\n",
    "                    return mid\n",
    "                if mid < n - 1:\n",
    "                    b = mountain_arr.get(mid + 1)\n",
    "                    if a < b:\n",
    "                        if a == target:\n",
    "                            return mid\n",
    "                        elif a < target:\n",
    "                            left = mid + 1\n",
    "                        else:\n",
    "                            right = mid - 1\n",
    "                    else:\n",
    "                        right = mid - 1\n",
    "                else:\n",
    "                    return mid if mountain_arr.get(mid) == target else -1\n",
    "            return -1\n",
    "        def find_right():\n",
    "            left, right = 0, n - 1\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                a = mountain_arr.get(mid)\n",
    "                if a == target:\n",
    "                    return mid\n",
    "                if mid > 0:\n",
    "                    b = mountain_arr.get(mid - 1)\n",
    "                    if b > a:\n",
    "                        if a < target:\n",
    "                            right = mid - 1\n",
    "                        else:\n",
    "                            left = mid + 1\n",
    "                    else:\n",
    "                        left = mid + 1\n",
    "                else:\n",
    "                    return mid if mountain_arr.get(mid) == target else -1\n",
    "            return -1\n",
    "        a = find_left()\n",
    "        if a == -1:\n",
    "            return find_right()\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        n = mountain_arr.length()\n",
    "        left, right = 0, n\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if mid + 1 < n and mountain_arr.get(mid + 1) > mountain_arr.get(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        top = left\n",
    "\n",
    "        left, right = 0, top + 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if mountain_arr.get(mid) < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        if left < top + 1 and mountain_arr.get(left) == target:\n",
    "            return left\n",
    "        \n",
    "        left, right = top + 1, n\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if mountain_arr.get(mid) > target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        if left < n and mountain_arr.get(left) == target:\n",
    "            return left\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        def asce(cur):\n",
    "            if cur == 0:\n",
    "                return True\n",
    "            l = cur - 1\n",
    "            return mountain_arr.get(l) < mountain_arr.get(cur)\n",
    "        #find peak, search in 2 ways\n",
    "        def findPeak():\n",
    "            l, r = -1, mountain_arr.length()\n",
    "            while l + 1 < r:\n",
    "                m = l + (r - l) // 2\n",
    "                if asce(m):\n",
    "                    l = m\n",
    "                else:\n",
    "                    r = m\n",
    "            return l\n",
    "        def binarySearch(left, right, target, isAsec):\n",
    "            l, r = left - 1, right + 1\n",
    "            while l + 1 < r:\n",
    "                m = l + (r - l) // 2\n",
    "                mid = mountain_arr.get(m)\n",
    "                if (isAsec and mid <= target) or (not isAsec and mid >= target):\n",
    "                    l = m\n",
    "                else:\n",
    "                    r = m\n",
    "            return l\n",
    "\n",
    "        peak = findPeak()\n",
    "        l = mountain_arr.length()\n",
    "        left = binarySearch(0,peak, target, True)\n",
    "        right = binarySearch(peak+1, l - 1, target, False)\n",
    "        # print(peak, left, right)\n",
    "        if 0 <= left <= peak and mountain_arr.get(left) == target: \n",
    "            return left\n",
    "        if peak + 1 <= right < l and mountain_arr.get(right) == target: \n",
    "            return right\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        lo , hi = 0,mountain_arr.length()-1\n",
    "        len_array = hi\n",
    "        while hi>lo:\n",
    "            mi = (hi+lo)//2\n",
    "            num1,num2,num3 =  mountain_arr.get(mi-1), mountain_arr.get(mi), mountain_arr.get(mi+1)\n",
    "            if num1<num2:#mountain_arr.get(mi):\n",
    "                if num2>num3:#mountain_arr.get(mi)>mountain_arr.get(mi+1):\n",
    "                    break\n",
    "                else:\n",
    "                    lo = mi+1\n",
    "            else:\n",
    "                hi = mi\n",
    "        top = mi\n",
    "        #left\n",
    "        lo,hi = 0,top\n",
    "        while hi>=lo:\n",
    "            mi = (hi+lo)//2\n",
    "            cur_val = mountain_arr.get(mi)\n",
    "            if cur_val<target:\n",
    "                lo = mi+1\n",
    "            elif cur_val>target:\n",
    "                hi = mi - 1\n",
    "            else:\n",
    "                lo = mi\n",
    "                break\n",
    "        if mountain_arr.get(lo)==target: return lo\n",
    "        lo,hi = top+1,len_array-1\n",
    "        while hi>=lo:\n",
    "            mi = (hi+lo)//2\n",
    "            cur_val = mountain_arr.get(mi)\n",
    "            if cur_val<target:\n",
    "                hi = mi - 1\n",
    "            elif cur_val>target:\n",
    "                lo = mi+1\n",
    "            else:\n",
    "                lo = mi\n",
    "                break\n",
    "        if mountain_arr.get(lo)==target: return lo\n",
    "        return -1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        \n",
    "        n = mountain_arr.length()\n",
    "\n",
    "        # find the peak\n",
    "\n",
    "        low = 1\n",
    "        high = n - 2\n",
    "        peak_idx = 0\n",
    "        ## 會逐漸逼近peak\n",
    "        while low != high:\n",
    "            mid = (low + high) // 2\n",
    "            \n",
    "            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid        \n",
    "        peak_idx = low\n",
    "\n",
    "        # find the left side\n",
    "        low = 0\n",
    "        high = peak_idx\n",
    "\n",
    "        while low != high:\n",
    "            mid = (low+high) // 2\n",
    "            if mountain_arr.get(mid) < target:\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid\n",
    "\n",
    "        if mountain_arr.get(low) == target:\n",
    "            return low\n",
    "        \n",
    "        # find the right side\n",
    "        low = peak_idx + 1\n",
    "        high = n-1\n",
    "        print(low, high)        \n",
    "        while low != high:\n",
    "            mid = (low+high) // 2\n",
    "            if mountain_arr.get(mid) > target:\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid\n",
    "        if mountain_arr.get(low) == target:\n",
    "            return low\n",
    "        \n",
    "        return -1\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        length = mountain_arr.length()\n",
    "        left, right = 0, length - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        \n",
    "        peek = left\n",
    "\n",
    "        left, right = 0, peek\n",
    "        idx = -1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            num = mountain_arr.get(mid)\n",
    "            if num == target:\n",
    "                idx = mid\n",
    "                break\n",
    "            elif num > target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        if idx != -1:\n",
    "            return idx\n",
    "        left = peek + 1\n",
    "        right = length - 1\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            num = mountain_arr.get(mid)\n",
    "            if num == target:\n",
    "                idx = mid\n",
    "                break\n",
    "            elif num > target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        if idx != -1:\n",
    "            return idx\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        def searchPeak(mountain_arr):\n",
    "            left, right = 0, mountain_arr.length()-1\n",
    "            while left<right:\n",
    "                mid = left+(right-left)//2\n",
    "                if mountain_arr.get(mid)<mountain_arr.get(mid+1):\n",
    "                    left = mid+1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return left\n",
    "\n",
    "        def binarySearch(mountain_arr, left, right, target, is_increasing=True):\n",
    "            while left<=right:\n",
    "                mid = left+(right-left)//2\n",
    "                midValue = mountain_arr.get(mid)\n",
    "                if target==midValue:\n",
    "                    return mid\n",
    "                elif target>midValue:\n",
    "                    if is_increasing:\n",
    "                        left=mid+1\n",
    "                    else:\n",
    "                        right=mid-1\n",
    "                else:\n",
    "                    if is_increasing:\n",
    "                        right=mid-1\n",
    "                    else:\n",
    "                        left=mid+1\n",
    "            return -1\n",
    "\n",
    "        peakValue = searchPeak(mountain_arr)\n",
    "        first = binarySearch(mountain_arr, 0, peakValue, target, is_increasing=True)\n",
    "        if first!=-1:\n",
    "            return first\n",
    "\n",
    "        second = binarySearch(mountain_arr, peakValue+1, mountain_arr.length()-1, target,is_increasing=False)\n",
    "        return second"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        \n",
    "        # 找到峰值\n",
    "        def check(x):\n",
    "            return mountain_arr.get(x+1) - mountain_arr.get(x) < 0\n",
    "        \n",
    "        n = mountain_arr.length()\n",
    "\n",
    "        l, r = 1, n-1\n",
    "        while l < r:\n",
    "            mid  = l + r >> 1\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        peek = l\n",
    "\n",
    "        # 在左边找>=peek的最小\n",
    "        if mountain_arr.get(peek) < target:\n",
    "            return -1\n",
    "\n",
    "        l, r = 0, peek\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if mountain_arr.get(mid) >= target:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        print(l)\n",
    "        # 查看找到的l是不是=target\n",
    "        if mountain_arr.get(l) == target:\n",
    "            return l\n",
    "        \n",
    "        # 否则在右边找<=target的最小\n",
    "        if mountain_arr.get(n-1) > target:\n",
    "            return -1\n",
    "\n",
    "        l, r = peek, n-1\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if mountain_arr.get(mid) <= target:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        if mountain_arr.get(l) == target:\n",
    "            return l\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "def binary_search(mountain, target, l, r, key=lambda x: x):\n",
    "    target = key(target)\n",
    "    while l <= r:\n",
    "        mid = (l + r) // 2\n",
    "        cur = key(mountain.get(mid))\n",
    "        if cur == target: \n",
    "            return mid\n",
    "        elif cur < target:\n",
    "            l = mid + 1\n",
    "        else:\n",
    "            r = mid - 1\n",
    "    return -1\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        l, r = 0, mountain_arr.length() - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        peak = l \n",
    "        index = binary_search(mountain_arr, target, 0, peak)\n",
    "        if index != -1:\n",
    "            return index\n",
    "        index = binary_search(mountain_arr, target, peak + 1, mountain_arr.length() - 1, lambda x: -x)\n",
    "        return index\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        n = mountain_arr.length()\n",
    "        l,r = 0,n - 1\n",
    "        while l + 1 < r:\n",
    "            mid = (l + r) >> 1\n",
    "            a,b,c = mountain_arr.get(mid - 1),mountain_arr.get(mid),mountain_arr.get(mid + 1)\n",
    "            if a < b < c:\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        if mountain_arr.get(r) == target:\n",
    "            return r\n",
    "\n",
    "        def check(l,r):\n",
    "            while l + 1 < r:\n",
    "                mid = (l + r) >> 1\n",
    "                x = mountain_arr.get(mid)\n",
    "                if x < target:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid\n",
    "            return r if r < n and mountain_arr.get(r) == target else -1\n",
    "\n",
    "        def check1(l,r):\n",
    "            while l + 1 < r:\n",
    "                mid = (l + r) >> 1\n",
    "                x = mountain_arr.get(mid)\n",
    "                if x > target:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid\n",
    "            return r if r < n and mountain_arr.get(r) == target else -1\n",
    "        \n",
    "        left = check(-1,r)\n",
    "        if left != -1:\n",
    "            return left\n",
    "        right = check1(r,n)\n",
    "        if right != -1:\n",
    "            return right\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is MountainArray's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class MountainArray:\n",
    "#    def get(self, index: int) -> int:\n",
    "#    def length(self) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:\n",
    "        def binary_search(mountain_arr,target,start,end,asc=True):\n",
    "            while start+1<end:\n",
    "                mid=(start+end)//2\n",
    "                mid_val=mountain_arr.get(mid)\n",
    "                if mid_val==target:\n",
    "                    return mid\n",
    "                if asc:\n",
    "                    if mid_val<target:\n",
    "                        start=mid\n",
    "                    else:\n",
    "                        end=mid\n",
    "                else:\n",
    "                    if mid_val<target:\n",
    "                        end=mid\n",
    "                    else:\n",
    "                        start=mid                 \n",
    "            if mountain_arr.get(start)==target:\n",
    "                return start\n",
    "            if mountain_arr.get(end)==target:\n",
    "                return end               \n",
    "            return -1\n",
    "        \n",
    "        start,end=0,mountain_arr.length()-1      \n",
    "        while start+1<end:\n",
    "            mid=(start+end)//2\n",
    "            if mountain_arr.get(mid)>=mountain_arr.get(mid+1):\n",
    "                end=mid\n",
    "            else:\n",
    "                start=mid\n",
    "        if mountain_arr.get(start)>=mountain_arr.get(end):\n",
    "            peak=start\n",
    "        else:\n",
    "            peak=end\n",
    "        index=binary_search(mountain_arr,target,0,peak,True)\n",
    "        if index!=-1:\n",
    "            return index\n",
    "        index=binary_search(mountain_arr,target,peak+1,mountain_arr.length()-1, asc=False)\n",
    "        return index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\r\n",
    "# This is MountainArray's API interface.\r\n",
    "# You should not implement it, or speculate about its implementation\r\n",
    "# \"\"\"\r\n",
    "#class MountainArray:\r\n",
    "#    def get(self, index: int) -> int:\r\n",
    "#    def length(self) -> int:\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def findInMountainArray(self, target: int, arr: 'MountainArray') -> int:\r\n",
    "        # arr[l] \r\n",
    "\r\n",
    "        l, r = 0, arr.length() - 1\r\n",
    "        while l + 1 < r:\r\n",
    "            mid = l + (r - l) // 2 \r\n",
    "            if arr.get(mid) > arr.get(mid - 1):\r\n",
    "                l = mid\r\n",
    "            else :\r\n",
    "                r = mid \r\n",
    "        # l 是峰顶  zai [0, l] 和 [l + 1, arr.length() - 1] 进行两次二分查找 \r\n",
    "        ll, rr = 0, l\r\n",
    "        while  ll <= rr :\r\n",
    "            mid = ll + (rr - ll) // 2 \r\n",
    "            x = arr.get(mid)\r\n",
    "            if x == target:\r\n",
    "                return mid \r\n",
    "            elif x > target:\r\n",
    "                rr = mid - 1\r\n",
    "            else:\r\n",
    "                ll = mid + 1 \r\n",
    "        ll, rr = l + 1, arr.length() - 1\r\n",
    "        while  ll <= rr :\r\n",
    "            mid = ll + (rr - ll) // 2 \r\n",
    "            x = arr.get(mid)\r\n",
    "            if x == target:\r\n",
    "                return mid \r\n",
    "            elif x > target:\r\n",
    "                ll = mid + 1 \r\n",
    "            else:\r\n",
    "                rr = mid - 1 \r\n",
    "        return -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
